
struct ListNode
{
    int val;
    ListNode *next;
    ListNode() : val(0), next(nullptr) {}
    ListNode(int x) : val(x), next(nullptr) {}
    ListNode(int x, ListNode *next) : val(x), next(next) {}
};
#include <iostream>
#include <unordered_map>
using namespace std;
class Solution
{
public:
    typedef pair<ListNode *, ListNode *> PLL;
    PLL reverse(ListNode *cur, int k)
    {
        ListNode *newtail = cur;
        ListNode *pnode = new ListNode;
        while (k--)
        {
            // cout << cur->val << endl;
            ListNode *nextcur = cur->next;
            // cout << cur->next->val << endl;
            cur->next = pnode->next;
            pnode->next = cur;
            cur = nextcur;
        }
        cur = pnode->next;
        delete pnode;
        return {cur, newtail};
    }
    ListNode *reverseKGroup(ListNode *head, int k)
    {
        if (!head || !head->next || k == 1)
            return head;
        ListNode *phead = new ListNode;
        ListNode *cur = head;
        ListNode *newtail = phead;
        while (cur)
        {
            int num = k;

            // 先判断当前链表结点数量是否满足旋转
            ListNode *nowtail = cur;
            while (nowtail && --num)
                nowtail = nowtail->next;
            if (num)
                break;
            ListNode *nextcur = nowtail->next;
            // 如果不满足，说明不需要动，旋转完成
            // 满足，开始当前循环操作
            // cout << cur->val << endl;
            PLL ret = reverse(cur, k);
            newtail->next = ret.first;
            newtail = ret.second;

            // 进行下一次旋转
            cur = nextcur;
        }
        // 旋转完成之后，还需要将剩下的不需要旋转的部分链入新链表
        newtail->next = cur;
        head = phead->next;
        delete phead;
        return head;
    }
};